package leetcode.图.拓扑排序;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/8/6 23:40
 * @description：https://leetcode-cn.com/problems/course-schedule-ii/
 */
public class 课程表II {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(Arrays.toString(solution.findOrder(4, new int[][]{{1, 0}, {2, 0}, {3, 1}, {3, 2}})));
    }

    class Solution {
        List<List<Integer>> edges;
        int[] inDeg;
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            edges = new ArrayList<>();
            inDeg = new int[numCourses];
            for (int i = 0; i < numCourses; i++) {
                edges.add(new ArrayList<>());
            }
            for (int[] prerequisite : prerequisites) {
                edges.get(prerequisite[1]).add(prerequisite[0]);
                inDeg[prerequisite[0]]++;
            }
            Queue<Integer> queue = new LinkedList<>();
            for (int i = 0; i < inDeg.length; i++) {
                if (inDeg[i] == 0) {
                    queue.offer(i);
                }
            }
            int index = 0;
            int[] ans = new int[numCourses];
            while (!queue.isEmpty()) {
                Integer cur = queue.poll();
                ans[index++] = cur;
                for (Integer in : edges.get(cur)) {
                    if (--inDeg[in] == 0) {
                        queue.offer(in);
                    }
                }
            }
            return index == numCourses ? ans : new int[0];
        }
    }
}
